package binarySearch;

import beans.TreeNode;

/**
 * @author pengfei.hpf
 * @date 2020/2/21
 * @verdion 1.0.0
 * 给出一个完全二叉树，求出该树的节点个数。
 *
 * 说明：
 *
 * 完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 *
 * 示例:
 *
 * 输入:
 *     1
 *    / \
 *   2   3
 *  / \  /
 * 4  5 6
 *
 * 输出: 6
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class CountNodes {
    public int countNodes(TreeNode root){
        if(root == null){
            return 0;
        }
        int d = depth(root);
        if(d == 0){
            return 1;
        }
        int size = (int)Math.pow(2, d) -1;
        int left = 0;
        int right = size;
        int mid;
        while(left < right){
            mid = left + (right - left)/2;
            if(exists(root, mid, size, d)){
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return size + left+1;
    }

    private int depth(TreeNode node){
        int d = 0;
        while(node.left != null){
            d ++;
            node = node.left;
        }
        return d;
    }


    private boolean exists(TreeNode node, int idx, int size, int d){
        int l = 0;
        int r = size;
        int mid;
        for(int i = 0; i < d; i ++)
        {
            mid = l + (r - l)/2;
            if(mid > idx){
                r = mid;
                node = node.left;
            }else{
                l = mid + 1;
                node = node.right;
            }
        }
        return node != null;
    }
}
